# LeetCode 76、最小覆盖子串
# 一、题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105s和t由英文字母组成
**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗？
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最小覆盖子串（LeetCode 76）：https://leetcode.cn/problems/minimum-window-substring/
class Solution {
public static String minWindow(String s, String t) {
// 使用整型数组来表示每个字符在 t 中的数量，初始化都为 0，利用 ASCII 码的方式把字符存储到整型数组中
// 数组的长度设置为 128
// 其中 65 ～ 90 号为 26 个大写英文字母，97 ～ 122 号为 26 个小写英文字母，其余为一些标点符号、运算符号等
// 由于 t 是由英文字母组成，所以数组中有些位置的值始终不会被操作，造成了空间的浪费，比如 map[20]map[30]
// 但这样做方便理解，比如看到 map[98] = 5 ，能知道 b 出现的频次是 5 次
int[] map = new int[128];
// 开始统计 t 中每个字符出现的频次
for (int i = 0; i < t.length(); i++) {
// 对于数组类型，其下标为 int 类型
// 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
// 比如 t.charAt(i) = 'a'，存储的就是 map[97]
map[t.charAt(i)]++;
}
// 记录滑动窗口的长度，并且不断更新获取最小的那个
int windowLength = s.length() + 1;
// 滑动窗口的左端
int left = 0;
// 滑动窗口的右端
int right = 0;
// t 中字符的总个数
int count = t.length();
// 滑动窗口左端新的位置
int start = 0;
// 滑动窗口的右端开始移动
while (right < s.length()) {
// 获取此时将要加入到滑动窗口的元素
char c = s.charAt(right);
// 如果说 map 数组中 c 出现的频次大于了 0，说明此时字符 c 加入到滑动窗口距离找到这样一个子串更近了一步
// 那么滑动窗口需要搜罗的特定元素个数变少了
if (map[c] > 0) {
// 需要搜罗的和 t 中字符一样的元素个数变少了
count--;
}
// 既然滑动窗口中新增了一个字符 c，那么 map 数组中对应的频次就需要减 1
map[c]--;
System.out.println( c + " : " + map[c]);
// 如果此时 count == 0 ，表明滑动窗口中包含了 t 中全部的字符
// 此时，找到了一个符合条件的子串
// 但想尝试一下，能否满足条件的情况下子串更短一些
// 于是，去尝试把滑动窗口的左端向右移动一下
// 可以移动的前提是，滑动窗口的左端元素抛弃后剩下的元素依旧满足条件
// 意思就是实际上左端元素是多余的
// 而如果这个元素对应的值在 map[] 数组中小于 0，说明它是一个多余元素
// 反复的删除这些多余的元素
while(count == 0){
// 如果当前的这个窗口值比之前维护的窗口值更小，需要进行更新
if (right - left + 1 < windowLength) {
// 更新滑动窗口的长度
windowLength = right - left + 1;
// 更新滑动窗口起始位置，来到了 left 这个位置
start = left;
}
// 接下来左端位置开始向右移动，也就是一个删除操作
// 删除操作需要执行以下三个步骤
// 如果这个元素不是多余的元素，比如滑动窗口为 ADBC，t 为 ABC
// 移除了 A，那么滑动窗口又需要去新增其它的元素了
// 所以通过 map[s.charAt(left)] == 0 来判断它是否是多余的元素
if( map[s.charAt(left)] == 0){
// 需要搜罗的和 t 中字符一样的元素个数要增加一个了，因为删除了关键元素
count++;
}
// 2、这个元素离开了滑动窗口，那么在 map 中这个的值就需要加 1
// 对应着上面新增一个元素到滑动窗口，map[c]--
map[s.charAt(left)]++;
// 3、left 向右移动，那么这个元素就离开了
left++;
}
// 可以开始查看新的元素了
right++;
}
// 根据 s 中是否涵盖了 t 所有字符的子串来获取结果
return windowLength == s.length() + 1 ? "" : s.substring(start, start + windowLength);
}
}
# 2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最小覆盖子串（LeetCode 76）：https://leetcode.cn/problems/minimum-window-substring/
class Solution {
public:
string minWindow(string s, string t) {
// 使用整型数组来表示每个字符在 t 中的数量，初始化都为 0，利用 ASCII 码的方式把字符存储到整型数组中
// 数组的长度设置为 128
// 其中 65 ～ 90 号为 26 个大写英文字母，97 ～ 122 号为 26 个小写英文字母，其余为一些标点符号、运算符号等
// 由于 t 是由英文字母组成，所以数组中有些位置的值始终不会被操作，造成了空间的浪费，比如 map[20]map[30]
// 但这样做方便理解，比如看到 map[98] = 5 ，能知道 b 出现的频次是 5 次
vector<int> map(128, 0);
// 开始统计 t 中每个字符出现的频次
for (auto& c : t){
// 对于数组类型，其下标为 int 类型
// 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
// 比如 t.[i) = 'a'，存储的就是 map[97]
map[c]++;
}
// 记录滑动窗口的长度，并且不断更新获取最小的那个
int windowLength = s.length() + 1;
// 滑动窗口的左端
int left = 0;
// 滑动窗口的右端
int right = 0;
// t 中字符的总个数
int count = t.length();
// 滑动窗口左端新的位置
int start = 0;
// 滑动窗口的右端开始移动
while (right < s.length()) {
// 获取此时将要加入到滑动窗口的元素
auto c = s[right];
// 如果说 map 数组中 c 出现的频次大于了 0，说明此时字符 c 加入到滑动窗口距离找到这样一个子串更近了一步
// 那么滑动窗口需要搜罗的特定元素个数变少了
if (map[c] > 0) {
// 需要搜罗的和 t 中字符一样的元素个数变少了
count--;
}
// 既然滑动窗口中新增了一个字符 c，那么 map 数组中对应的频次就需要减 1
map[c]--;
// System.out.println( c + " : " + map[c]);
// 如果此时 count == 0 ，表明滑动窗口中包含了 t 中全部的字符
// 此时，找到了一个符合条件的子串
// 但想尝试一下，能否满足条件的情况下子串更短一些
// 于是，去尝试把滑动窗口的左端向右移动一下
// 可以移动的前提是，滑动窗口的左端元素抛弃后剩下的元素依旧满足条件
// 意思就是实际上左端元素是多余的
// 而如果这个元素对应的值在 map[] 数组中小于 0，说明它是一个多余元素
// 反复的删除这些多余的元素
while(count == 0){
// 如果当前的这个窗口值比之前维护的窗口值更小，需要进行更新
if (right - left + 1 < windowLength) {
// 更新滑动窗口的长度
windowLength = right - left + 1;
// 更新滑动窗口起始位置，来到了 left 这个位置
start = left;
}
// 接下来左端位置开始向右移动，也就是一个删除操作
// 删除操作需要执行以下三个步骤
// 如果这个元素不是多余的元素，比如滑动窗口为 ADBC，t 为 ABC
// 移除了 A，那么滑动窗口又需要去新增其它的元素了
// 所以通过 map[s.[left)] == 0 来判断它是否是多余的元素
if( map[s[left]] == 0){
// 需要搜罗的和 t 中字符一样的元素个数要增加一个了，因为删除了关键元素
count++;
}
// 2、这个元素离开了滑动窗口，那么在 map 中这个的值就需要加 1
// 对应着上面新增一个元素到滑动窗口，map[c]--
map[s[left]]++;
// 3、left 向右移动，那么这个元素就离开了
left++;
}
// 可以开始查看新的元素了
right++;
}
// 根据 s 中是否涵盖了 t 所有字符的子串来获取结果
return windowLength == s.length() + 1 ? "" : s.substr(start, windowLength);
}
};
# 3、Python 代码
class Solution:
def minWindow(self, s: str, t: str) -> str:
# 使用整型数组来表示每个字符在 t 中的数量，初始化都为 0，利用 ASCII 码的方式把字符存储到整型数组中
# 数组的长度设置为 128
# 其中 65 ～ 90 号为 26 个大写英文字母，97 ～ 122 号为 26 个小写英文字母，其余为一些标点符号、运算符号等
# 由于 t 是由英文字母组成，所以数组中有些位置的值始终不会被操作，造成了空间的浪费，比如 map[20]map[30]
# 但这样做方便理解，比如看到 map[98] = 5 ，能知道 b 出现的频次是 5 次
map = collections.defaultdict(int)
# 开始统计 t 中每个字符出现的频次
for ch in t: #初始化需要的必要字符数量
map[ch] += 1
# 记录滑动窗口的长度，并且不断更新获取最小的那个
windowLength = len(s) + 1
# 滑动窗口的左端
left = 0
# 滑动窗口的右端
right = 0
# t 中字符的总个数
count = len(t)
# 滑动窗口左端新的位置
start = 0
# 滑动窗口的右端开始移动
while right < len(s) :
# 获取此时将要加入到滑动窗口的元素
c = s[right]
# 如果说 map 数组中 c 出现的频次大于了 0，说明此时字符 c 加入到滑动窗口距离找到这样一个子串更近了一步
# 那么滑动窗口需要搜罗的特定元素个数变少了
if map[c] > 0 :
# 需要搜罗的和 t 中字符一样的元素个数变少了
count -= 1
# 既然滑动窗口中新增了一个字符 c，那么 map 数组中对应的频次就需要减 1
map[c] -= 1
# 如果此时 count == 0 ，表明滑动窗口中包含了 t 中全部的字符
# 此时，找到了一个符合条件的子串
# 但想尝试一下，能否满足条件的情况下子串更短一些
# 于是，去尝试把滑动窗口的左端向右移动一下
# 可以移动的前提是，滑动窗口的左端元素抛弃后剩下的元素依旧满足条件
# 意思就是实际上左端元素是多余的
# 而如果这个元素对应的值在 map[] 数组中小于 0，说明它是一个多余元素
# 反复的删除这些多余的元素
while count == 0 :
# 如果当前的这个窗口值比之前维护的窗口值更小，需要进行更新
if right - left + 1 < windowLength :
# 更新滑动窗口的长度
windowLength = right - left + 1
# 更新滑动窗口起始位置，来到了 left 这个位置
start = left
# 接下来左端位置开始向右移动，也就是一个删除操作
# 删除操作需要执行以下三个步骤
# 如果这个元素不是多余的元素，比如滑动窗口为 ADBC，t 为 ABC
# 移除了 A，那么滑动窗口又需要去新增其它的元素了
# 所以通过 map[s.charAt(left)] == 0 来判断它是否是多余的元素
if map[s[left]] == 0 :
# 需要搜罗的和 t 中字符一样的元素个数要增加一个了，因为删除了关键元素
count += 1
# 2、这个元素离开了滑动窗口，那么在 map 中这个的值就需要加 1
# 对应着上面新增一个元素到滑动窗口，map[c]--
map[s[left]] += 1
# 3、left 向右移动，那么这个元素就离开了
left += 1
# 可以开始查看新的元素了
right += 1
# 根据 s 中是否涵盖了 t 所有字符的子串来获取结果
return '' if windowLength == (len(s) + 1) else s[start:start + windowLength]
# 四、复杂度分析
时间复杂度： 两个指针都严格递增，最多移动 n 次，所以总时间复杂度是 O(n)。
空间复杂度：O(C)